package com.breeze.leetcode.hard;

import java.util.*;

/**
 * @url <a href="https://leetcode.cn/problems/cat-and-mouse/">913. 猫和老鼠</a>
 */
public class T913CatAndMouse {
    private int n;
    private int[][][] memo;
    public int catMouseGame(int[][] graph) {
        n = graph.length;
        // 初始化memo数组
        memo = new int[2 * n * n][n][n];
        for (int[][] memoItem : memo) {
            for (int[] row : memoItem) {
                Arrays.fill(row, -1);
            }
        }

        // 从 (步数 0, 老鼠在 1, 猫在 2) 开始搜索
        return dfs(0, 1, 2, graph);
    }

    private int dfs(int step, int mousePos, int catPos, int[][] graph) {
        // 如果该状态已经计算过，直接返回 question: 搜索过就代表答案吗
        if(memo[step][mousePos][catPos] != -1) {
            return memo[step][mousePos][catPos];
        }

        // 如果老鼠到达节点 0，表示老鼠胜利
        if (mousePos == 0) {
            return memo[step][mousePos][catPos] = 1;
        }

        // 如果老鼠和猫在同一位置，表示猫胜利
        if (mousePos == catPos) {
            return memo[step][mousePos][catPos] = 2;
        }

        // 如果步数已经超过最大步数，表示平局
        if (step >= 2 * n * (n - 1)) {
            return memo[step][mousePos][catPos] = 0;
        }

        // 老鼠开始行动
        if (step % 2 == 0) {
            boolean win = false, draw = false;
            for (int nextPos : graph[mousePos]) {
                int result = dfs(step + 1, nextPos, catPos, graph);
                if (result == 1) {
                    win = true;
                    break;
                } else if (result == 0) {
                    draw = true;
                }
            }
            // 优先赢，其次平局，最后输
            return memo[step][mousePos][catPos] = win ? 1 : (draw ? 0 : 2);
        } else {
            boolean win = false, draw = false;
            for (int nextPos : graph[catPos]) {
                if (nextPos == 0) {
                    continue;
                }
                int result = dfs(step + 1, mousePos, nextPos, graph);
                if (result == 2) {
                    win = true;
                    break;
                } else if (result == 0) {
                    draw = true;
                }
            }
            return memo[step][mousePos][catPos] = win ? 2 : (draw ? 0 : 1);
        }
    }
}
